
function insertionSort(arr) {
    var len = arr.length;
    var preIndex, current;
    for (var i = 1; i < len; i++) {
        preIndex = i - 1;
        current = arr[i];
        while(preIndex >= 0 && arr[preIndex] > current) {
            arr[preIndex+1] = arr[preIndex];
            preIndex--;
        }
        arr[preIndex+1] = current;
    }
    console.log('插入排序', arr);
}

function insertionSort1(arr) {
    let len = arr.length;
    let target = [arr[0]]
    for(let i = 1; i<len; i++) {
        for(let j = target.length; j>=0; j--) {
            if(arr[i] >= target[j]) {
                target.splice(j+1, 0, arr[i]);
                break;
            }
            if(j == 0){
                target.unshift(arr[i]);
            }
        }
    }
    console.log('插入排序', target);
}

insertionSort([5, 2, 3, 1,15,5,6,3]);
insertionSort1([5, 2, 3, 1,15,5,6,3]);
